#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class SubSumMatch:
    def __init__(self, array, sum):
        self.l = len(array) + 1
        self.sum = sum

        self.init(array)

        self.do()

    def init(self, array):
        # for i in range(self.sum+1):
        #     self.mat[0][i] = set()
        row = [0 for i in range(self.sum + 1)]
        self.mat = [list(row) for i in range(self.l)]

        for i in range(self.l):
            self.mat[i][0] = {0}

        # 方便offset 1取值
        self.array = [0] + array

    def do(self):
        # print(self.array)
        for i in range(1, self.l):
            for j in range(1, self.sum+1):
                self.check_cur(i, j)

    def check_cur(self, i, j):
        cur_v = self.array[i]

        if i == 4 and j == 11:
            print(i, j)
            print('hit')
            print(cur_v)
            # print()
            print(self.mat[i-1][j-cur_v])

        s = set()
        if self.mat[i-1][j]:
            # 不包含当前元素
            s.add('up')

        if cur_v <= j:
            # 包含当前元素
            if self.mat[i-1][j-cur_v]:
                s.add('cur')

        if s:
            self.mat[i][j] = s

    def __str__(self):
        return str(self.mat)

    def show(self):
        for i in self.mat:
            print(i)

    def travel_solution(self):
        self.sln = []
        if not self.mat[self.l-1][self.sum]:
            return None

        self._travel(self.l-1, self.sum, [])

        print('solution ===================  =====================')
        print(len(self.sln))
        for i in self.sln:
            print(i)

    def _travel(self, i, j, pre):
        # try:
        s = self.mat[i][j]
        assert(s)
        # except Exception as e:
        #     print('failed', i, j)
        #     return

        # if j == 0 or i == 0:
        if j == 0:
            self.sln.append(pre)
            return

        for sln in s:
            if sln == "up":
                self._travel(i-1, j, pre)
                return
            else:
                # cur
                cur_v = self.array[i]
                self._travel(i-1, j-cur_v, [cur_v] + pre)

def test():
    # array = [1,2,3,4,5,6]
    array = [2, 3, 7, 8, 10]
    # array = [1,2,3,]
    s = SubSumMatch(array, 11)
    s.show()
    s.travel_solution()


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
